Background: Mother-to-child transmission (MTCT) of Human immunodeficiency virus (HIV) through breastfeeding remains the most significant route infection among children. Although the current guideline is recommending continued breastfeeding for HIV exposed infants, significant proportion of infants have been subjected to early weaning to prevent HIV transmission. However the predictors of breastfeeding cessation among HIV positive mothers were not documented in Ethiopia. Therefore the objective of this study was to determine the predictors of breastfeeding cessation among HIV-infected women in Southern Ethiopia. Methods: A facility based cross sectional study was conducted in Southern Ethiopia. The samples were selected by cluster sampling technique. The Kaplan-Meier curve was used to describe the survival time of breastfeeding and a step-wise multivariable Cox-proportional hazards regression model were used to identify the predictors of breastfeeding cessation. Both crude and adjusted hazard ratio were determined and p<0.05 was considered as statistically significant. Result: The mean duration of breastfeeding among HIV positive mothers was 13.79 [95% CI: (12.97–14.59)] months. The Kaplan-Meier estimate showed that proportions of women who were breastfeeding at 6, 9, 12 and 17 months were 89.3%, 75.3%, 66% and 17%, respectively. Those mothers having a monthly income of ≤500 ETB [AHR = 0.16, 95% CI :(0.03–0.76)], having a family size of three and below [AHR = 0.12, 95%CI: (0.02–0.68), four and above [AHR = 0.07, 95%CI: (0.01–0.35)] and bottle feeding [AHR = 3.95, 95%CI: (1.64–9.51)] were also independent factors associated with breastfeeding cessation. Conclusion: Above one third of HIV positive mothers stopped breastfeeding before 12 months. Monthly income, bottle feeding and family size were the independent predictors of breastfeeding cessations. Strengthening the current counseling and promotion modality on avoidance of bottle feeding and continued breastfeeding is recommended for improved HIV free survival.